package com.lry.concurrent.locks;

import sun.misc.Unsafe;
import java.io.Serializable;
import java.lang.reflect.Field;
import java.util.concurrent.locks.LockSupport;

public class AbstractQueuedSynchronizer extends AbstractOwnableSynchronizer implements Serializable {


    private static final long serialVersionUID = 7373984972572414691L;

    static final long spinForTimeoutThreshold = 1000L;

    protected AbstractQueuedSynchronizer() {}


    public static Unsafe getUnsafeInstance()
    {
        Field theUnsafeInstance = null;
        try {
            theUnsafeInstance = Unsafe.class.getDeclaredField("theUnsafe");
            theUnsafeInstance.setAccessible(true);
            return (Unsafe) theUnsafeInstance.get(Unsafe.class);
        } catch (Exception e) {
            e.printStackTrace();
        }
        return null;
    }

    private static final Unsafe unsafe = getUnsafeInstance();
    private static final long stateOffset;
    private static final long headOffset;
    private static final long tailOffset;
    private static final long waitStatusOffset;
    private static final long nextOffset;
    static {
        try{
            stateOffset = unsafe.objectFieldOffset(AbstractQueuedSynchronizer.class.getDeclaredField("state"));
            headOffset = unsafe.objectFieldOffset(AbstractQueuedSynchronizer.class.getDeclaredField("head"));
            tailOffset = unsafe.objectFieldOffset(AbstractQueuedSynchronizer.class.getDeclaredField("tail"));
            waitStatusOffset = unsafe.objectFieldOffset
                    (AbstractQueuedSynchronizer.Node.class.getDeclaredField("waitStatus"));
            nextOffset = unsafe.objectFieldOffset
                    (AbstractQueuedSynchronizer.Node.class.getDeclaredField("next"));
        }catch (Exception ex){
            throw new Error(ex);
        }
    }


    static final class Node{

        static final Node SHARED = new Node();

        static final Node EXCLUSIVE = null;

        static final int CANCELLED = 1;

        static final int SIGNAL = -1;

        static final int CONDITION = -2;

        static final int PROPAGATE = -3;

        volatile int waitStatus;

        volatile Node prev;

        volatile Node next;

        volatile Thread thread;

        Node nextWaiter;

        final boolean isShared(){
            return nextWaiter == SHARED;
        }

        final Node predecessor() throws NullPointerException {
            Node p = prev;
            if(null==p){
                throw new NullPointerException();
            }
            return p;
        }

        Node(){} // Used to establish initial head or SHARED marker

        Node(Thread thread,Node node){// Used by addWaiter
            this.nextWaiter = node;
            this.thread = thread;
        }

        Node(Thread thread, int waitStatus) { // Used by Condition
            this.waitStatus = waitStatus;
            this.thread = thread;
        }
    }

    private transient volatile Node head;

    private transient volatile Node tail;

    private volatile int state;

    protected final int getState(){
        return state;
    }

    protected final void setState(int newState) {
        state = newState;
    }

    protected final boolean compareAndSetState(int expect,int update){
        return unsafe.compareAndSwapInt(this,stateOffset,expect,update);
    }

    private final boolean compareAndSetHead(Node update) {
        return unsafe.compareAndSwapObject(this, headOffset, null, update);
    }

    private final boolean compareAndSetTail(Node expect,Node update) {
        return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
    }

    private static final boolean compareAndSetWaitStatus(Node node,
                                                         int expect,
                                                         int update) {
        return unsafe.compareAndSwapInt(node, waitStatusOffset,
                expect, update);
    }

    /**
     * CAS next field of a node.
     */
    private static final boolean compareAndSetNext(Node node,
                                                   Node expect,
                                                   Node update) {
        return unsafe.compareAndSwapObject(node, nextOffset, expect, update);
    }

    public final void acquire(int count){
        if (!tryAcquire(count) &&
                acquireQueued(addWaiter(Node.EXCLUSIVE), count)){
            //补中断，让线程有响应中断的能力
            selfInterrupt();
        }

    }

    protected boolean tryRelease(int arg) {
        throw new UnsupportedOperationException();
    }

    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            AbstractQueuedSynchronizer.Node h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);
            return true;
        }
        return false;
    }


    private void cancelAcquire(Node node) {
        // Ignore if node doesn't exist
        if (node == null)
            return;

        node.thread = null;

        // Skip cancelled predecessors
        //往前跳过cancelled状态的节点，直到挂在一个非cancelled状态的节点后面
        Node pred = node.prev;
        while (pred.waitStatus > 0)
            node.prev = pred = pred.prev;

        // predNext is the apparent node to unsplice. CASes below will
        // fail if not, in which case, we lost race vs another cancel
        // or signal, so no further action is necessary.
        Node predNext = pred.next;

        // Can use unconditional write instead of CAS here.
        // After this atomic step, other Nodes can skip past us.
        // Before, we are free of interference from other threads.
        node.waitStatus = Node.CANCELLED;

        // If we are the tail, remove ourselves.
        //如果自己是尾节点，把前驱改为尾节点
        if (node == tail && compareAndSetTail(node, pred)) {
            compareAndSetNext(pred, predNext, null);
        } else {
            // If successor needs signal, try to set pred's next-link
            // so it will get one. Otherwise wake it up to propagate.
            int ws;
            if (pred != head &&
                    ((ws = pred.waitStatus) == Node.SIGNAL ||
                            (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
                    pred.thread != null) {
                Node next = node.next;
                if (next != null && next.waitStatus <= 0)
                    compareAndSetNext(pred, predNext, next);
            } else {
                unparkSuccessor(node);
            }

            node.next = node; // help GC
        }
    }

    private void unparkSuccessor(AbstractQueuedSynchronizer.Node node) {

        int ws = node.waitStatus;
        if (ws < 0)
            compareAndSetWaitStatus(node, ws, 0);

        AbstractQueuedSynchronizer.Node s = node.next;
        while (s != null && s.waitStatus > 0) {
           s = s.next;
        }
        if (s != null)
            LockSupport.unpark(s.thread);
    }

//    private void unparkSuccessor(AbstractQueuedSynchronizer.Node node) {
//        /*
//         * If status is negative (i.e., possibly needing signal) try
//         * to clear in anticipation of signalling.  It is OK if this
//         * fails or if status is changed by waiting thread.
//         */
//        int ws = node.waitStatus;
//        if (ws < 0)
//            compareAndSetWaitStatus(node, ws, 0);
//
//        /*
//         * Thread to unpark is held in successor, which is normally
//         * just the next node.  But if cancelled or apparently null,
//         * traverse backwards from tail to find the actual
//         * non-cancelled successor.
//         */
//        AbstractQueuedSynchronizer.Node s = node.next;
//        if (s == null || s.waitStatus > 0) {
//            s = null;
//            for (AbstractQueuedSynchronizer.Node t = tail; t != null && t != node; t = t.prev)
//                if (t.waitStatus <= 0)
//                    s = t;
//        }
//        if (s != null)
//            LockSupport.unpark(s.thread);
//    }

    final boolean acquireQueued(final Node node,int count){
        boolean failed = true;
        try{
            boolean interrupted = false;

            for(;;){
                final Node p = node.predecessor();
                if(p==head && tryAcquire(count)){
                    setHead(node);
                    p.next = null;
                    failed = false;
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt()){
                    interrupted = true;
                }
            }
        }finally {
            if(failed){
                //子类实现tryAcquire异常时会走取消逻辑
                cancelAcquire(node);
            }
        }
    }



    private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
        int ws = pred.waitStatus;
        if(ws == Node.SIGNAL){
            /*
             * This node has already set status asking a release
             * to signal it, so it can safely park.
             */
            return true;
        }

        if(ws > 0){//CANCELLED
            /*
             * Predecessor was cancelled. Skip over predecessors and
             * indicate retry.
             */

            do{
                pred = pred.prev;
                node.prev = pred;
            }while (pred.waitStatus > 0);
            pred.next = node;
        }else{
            /*
             * waitStatus must be 0 or PROPAGATE.  Indicate that we
             * need a signal, but don't park yet.  Caller will need to
             * retry to make sure it cannot acquire before parking.
             */

            compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
        }

        return false;
    }
    private void setHeadAndPropagate(AbstractQueuedSynchronizer.Node node, int propagate) {
        AbstractQueuedSynchronizer.Node h = head; // Record old head for check below
        setHead(node);

        if (propagate > 0 || h == null || h.waitStatus < 0 ||
                (h = head) == null || h.waitStatus < 0) {
            Node s = node.next;
            if (s == null || s.isShared()){
                doReleaseShared();
            }
        }
    }

    //jdk6u11
//    private void setHeadAndPropagate(AbstractQueuedSynchronizer.Node node, int propagate) {
//        AbstractQueuedSynchronizer.Node h = head; // Record old head for check below
//        setHead(node);
//
//        //jdk6u11
//        if (propagate > 0 && node.waitStatus != 0) {
//            Node s = node.next;
//            if (s == null || s.isShared())
//                unparkSuccessor(node);
//        }
//    }

    public final void acquireShared(int arg) {
        if (tryAcquireShared(arg) < 0)
            doAcquireShared(arg);
    }

    //jdk6u11
//    public final boolean releaseShared(int arg) {
//        if (tryReleaseShared(arg)) {
//            AbstractQueuedSynchronizer.Node h = head;
//            if (h != null && h.waitStatus != 0)
//                unparkSuccessor(h);
//            return true;
//        }
//        return false;
//    }

    public final boolean releaseShared(int arg) {
        if (tryReleaseShared(arg)) {
            doReleaseShared();
            return true;
        }
        return false;
    }

    protected boolean tryReleaseShared(int arg) {
        throw new UnsupportedOperationException();
    }

    private void doAcquireShared(int arg) {
        final AbstractQueuedSynchronizer.Node node = addWaiter(AbstractQueuedSynchronizer.Node.SHARED);
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (;;) {
                final AbstractQueuedSynchronizer.Node p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        if (interrupted)
                            selfInterrupt();
                        failed = false;
                        return;
                    }
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

    protected int tryAcquireShared(int arg) {
        throw new UnsupportedOperationException();
    }

    private void doReleaseShared() {

        for (;;) {
            Node h = head;
            if (h != null && h != tail) {
                int ws = h.waitStatus;
                if (ws == Node.SIGNAL) {
                    if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                        continue;            // loop to recheck cases
                    unparkSuccessor(h);
                }
                else if (ws == 0 &&
                        !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                    continue;                // loop on failed CAS
            }
            //继续向后唤醒节点
            if (h == head)                   // loop if head changed
                break;
        }
    }

    private final boolean parkAndCheckInterrupt() {
        //阻塞当前线程
        LockSupport.park(this);
        //清中断，返回清除之前的中断标志,为什么要清中断? 为了外部调用中断时，第二次park这里可以park住，不让cpu空转
//        return true;
        return Thread.interrupted();
    }

    private void setHead(Node node) {
        head = node;
        node.thread = null;
        node.prev = null;
    }

    private Node addWaiter(Node mode){
        //新建一个节点
        Node node = new Node(Thread.currentThread(),mode);

        //如果存在尾节点
        Node pred = tail;
        if(null!=pred){
            //新节点的前驱为tail
            node.prev = pred;
            //设置新节点为tail
            if(compareAndSetTail(pred,node)){
                //之前的尾节点next指向新尾节点
                pred.next = node;
                return node;
            }
        }
        enq(node);
        return node;
    }

    private Node enq(final Node node){
        for(;;){
            Node t = tail;
            if(null==t){
                if(compareAndSetHead(new Node())){
                    tail = head;//头尾都是新建的Node
                }
            }else{
                node.prev = t;
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
    }


    final int fullyRelease(Node node){
        boolean failed = true;
        try{
            int savedState = getState();
            if(release(savedState)){
                failed = false;
                return savedState;
            }else{
                throw new IllegalMonitorStateException();
            }
        }finally {
            if(failed){
                node.waitStatus = Node.CANCELLED;
            }
        }
    }

    final boolean isOnSyncQueue(Node node){
        if(node.waitStatus==Node.CONDITION || node.prev ==null){
            return false;
        }
        if (node.next != null) {
            return true;
        }
        return findNodeFromTail(node);
    }

    private boolean findNodeFromTail(Node node) {
        Node t = tail;
        for(;;){
            if(t==node){
                return true;
            }
            if(t==null){
                return false;
            }
            t = t.prev;
        }
    }

    static void selfInterrupt() {
        Thread.currentThread().interrupt();
    }

    protected boolean isHeldExclusively() {
        throw new UnsupportedOperationException();
    }

    protected boolean tryAcquire(int count) {
        throw new UnsupportedOperationException();
    }


    public class ConditionObject implements Condition,Serializable{

        private transient Node firstWaiter;
        private transient Node lastWaiter;



        @Override
        public void await() throws InterruptedException {
            if (Thread.interrupted()){
                throw new InterruptedException();
            }
            //添加一个新节点（thread,condition）到等待队列
            Node node = addConditionWaiter();
            //将state状态全部释放掉，最后应该是0
            int savedState = fullyRelease(node);

            //如果不在同步队列中，则park住当前线程
            while(!isOnSyncQueue(node)){
                LockSupport.park(this);
            }
            acquireQueued(node, savedState);
        }

        private Node addConditionWaiter(){
            Node t = lastWaiter;

            if (t != null && t.waitStatus != Node.CONDITION) {
                unlinkCancelledWaiters();
                t = lastWaiter;
            }


            Node node = new Node(Thread.currentThread(),Node.CONDITION);
            if(null == t){
                firstWaiter = node;
            }else{
                t.nextWaiter = node;
            }
            lastWaiter = node;
            return node;
        }

        private void unlinkCancelledWaiters(){

        }
        @Override
        public void awaitUninterruptibly() {

        }

        @Override
        public void signal() {
            if(!isHeldExclusively()){
                throw new IllegalMonitorStateException();
            }

            Node first = firstWaiter;
            if(null!=first){
                doSignal(first);
            }
        }

        private void doSignal(Node first) {
            //do while,会先走do里面的逻辑，再对while进行判断
            do{
                //firstWaiter指向下一个节点
                if((firstWaiter = first.nextWaiter)==null){
                    //如果下个节点为空，则firstWaiter和lastWaiter都赋值为null
                    lastWaiter = null;
                }
                first.nextWaiter = null;
                //transferForSignal失败了，则将first指向下个节点，不为空的话继续循环
            }while(!transferForSignal(first) &&
                    (first = firstWaiter) != null);

        }

        final boolean transferForSignal(Node node) {
            //如果节点是取消状态，则返回false，继续唤醒下一个节点
            if(!compareAndSetWaitStatus(node,Node.CONDITION,0)){
                return false;
            }
            //node入同步队列，返回之前的tail节点p
            Node p = enq(node);

            int ws = p.waitStatus;

            //cas 将node的前驱节点改为-1，如果修改失败了，直接unpark
            if(ws>0 || !compareAndSetWaitStatus(p,ws,Node.SIGNAL)){
                LockSupport.unpark(node.thread);
            }
            return true;
        }

        @Override
        public void signalAll() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            Node first = firstWaiter;
            if (first != null)
                doSignalAll(first);
        }

        private void doSignalAll(Node first) {
            lastWaiter = firstWaiter = null;
            do {
                Node next = first.nextWaiter;
                first.nextWaiter = null;
                transferForSignal(first);
                first = next;
            } while (first != null);
        }
    }

}
